#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define PROCESSES 5 // 进程数量
#define RESOURCES 3 // 资源类型数量

int available[RESOURCES];             // 可用资源向量
int max[PROCESSES][RESOURCES];        // 最大需求矩阵
int allocation[PROCESSES][RESOURCES]; // 分配矩阵
int need[PROCESSES][RESOURCES];       // 需求矩阵
bool finished[PROCESSES];             // 标记进程是否完成

// 初始化系统状态
void initialize()
{
    // 可用资源实例数 (A/B/C)
    available[0] = 3;
    available[1] = 3;
    available[2] = 2;

    // 最大需求矩阵 (每个进程对每种资源的最大需求)
    int max_init[PROCESSES][RESOURCES] = {
        {7, 5, 3}, // P0
        {3, 2, 2}, // P1
        {9, 0, 2}, // P2
        {2, 2, 2}, // P3
        {4, 3, 3}  // P4
    };

    // 分配矩阵 (已分配给每个进程的资源)
    int alloc_init[PROCESSES][RESOURCES] = {
        {0, 1, 0}, // P0
        {2, 0, 0}, // P1
        {3, 0, 2}, // P2
        {2, 1, 1}, // P3
        {0, 0, 2}  // P4
    };

    // 初始化数据结构
    for (int i = 0; i < PROCESSES; i++)
    {
        for (int j = 0; j < RESOURCES; j++)
        {
            max[i][j] = max_init[i][j];
            allocation[i][j] = alloc_init[i][j];
            need[i][j] = max[i][j] - allocation[i][j];
        }
        finished[i] = false;
    }
}

// 打印当前系统状态
void print_state()
{
    printf("\n当前系统状态:\n");
    printf("可用资源: [");
    for (int i = 0; i < RESOURCES; i++)
    {
        printf(" %d", available[i]);
    }
    printf(" ]\n\n");

    printf("进程\t最大需求   已分配\t需要\n");
    for (int i = 0; i < PROCESSES; i++)
    {
        printf("P%d\t", i);
        // 最大需求
        for (int j = 0; j < RESOURCES; j++)
        {
            printf("%d ", max[i][j]);
        }
        printf("\t");
        // 已分配
        for (int j = 0; j < RESOURCES; j++)
        {
            printf("%d ", allocation[i][j]);
        }
        printf("\t");
        // 需要
        for (int j = 0; j < RESOURCES; j++)
        {
            printf("%d ", need[i][j]);
        }
        printf("\n");
    }
}

// 安全性检查算法
bool is_safe()
{
    int work[RESOURCES];
    bool finish[PROCESSES];
    int safe_seq[PROCESSES];
    int count = 0;

    // 初始化工作向量和完成标记
    for (int i = 0; i < RESOURCES; i++)
    {
        work[i] = available[i];
    }
    for (int i = 0; i < PROCESSES; i++)
    {
        finish[i] = finished[i];
    }

    // 查找可以执行的进程
    while (count < PROCESSES)
    {
        bool found = false;
        // 一遍查找
        for (int i = 0; i < PROCESSES; i++)
        {
            if (!finish[i])
            {
                bool can_execute = true;

                // 检查当前进程的所有资源需求是否满足
                for (int j = 0; j < RESOURCES; j++)
                {
                    if (need[i][j] > work[j])
                    {
                        can_execute = false;
                        break;
                    }
                }

                if (can_execute)
                {
                    // 模拟执行进程并释放资源
                    for (int j = 0; j < RESOURCES; j++)
                    {
                        work[j] += allocation[i][j];
                    }

                    safe_seq[count] = i;
                    count++;
                    finish[i] = true;
                    found = true;
                }
            }
        }

        // 如果没有找到可执行的进程，系统处于不安全状态
        if (!found)
        {
            printf("\n系统处于不安全状态!\n");
            return false;
        }
    }

    // 打印安全序列
    printf("\n安全序列: ");
    for (int i = 0; i < PROCESSES; i++)
    {
        printf("P%d ", safe_seq[i]);
    }
    printf("\n");

    return true;
}

// 资源请求算法
bool request_resources(int pid, int request[])
{
    // 检查请求是否超过声明最大需求
    for (int i = 0; i < RESOURCES; i++)
    {
        if (request[i] > need[pid][i])
        {
            printf("错误: 请求超过声明的最大需求!\n");
            return false;
        }
    }

    // 检查系统是否有足够资源
    for (int i = 0; i < RESOURCES; i++)
    {
        if (request[i] > available[i])
        {
            printf("错误: 资源不足，进程必须等待!\n");
            return false;
        }
    }

    // 尝试分配资源
    for (int i = 0; i < RESOURCES; i++)
    {
        available[i] -= request[i];
        allocation[pid][i] += request[i];
        need[pid][i] -= request[i];
    }

    // 检查分配后系统是否安全
    if (is_safe())
    {
        printf("请求被批准，系统仍处于安全状态。\n");
        // 检查进程是否已完成
        bool done = true;
        for (int i = 0; i < RESOURCES; i++)
        {
            if (need[pid][i] != 0)
            {
                done = false;
                break;
            }
        }
        if (done)
        {
            printf("进程 P%d 已完成，释放所有资源。\n", pid);
            finished[pid] = true;
            for (int i = 0; i < RESOURCES; i++)
            {
                available[i] += allocation[pid][i];
                allocation[pid][i] = 0;
            }
        }
        return true;
    }
    else
    {
        // 回滚分配
        printf("请求会导致系统不安全，分配被拒绝。\n");
        for (int i = 0; i < RESOURCES; i++)
        {
            available[i] += request[i];
            allocation[pid][i] -= request[i];
            need[pid][i] += request[i];
        }
        return false;
    }
}

// 主函数
int main()
{
    initialize();
    print_state();
    is_safe(); // 初始安全检查

    int choice;
    do
    {
        printf("\n银行家算法模拟\n");
        printf("1. 请求资源\n");
        printf("2. 显示当前状态\n");
        printf("3. 退出\n");
        printf("请选择操作: ");
        scanf("%d", &choice);

        switch (choice)
        {
        case 1:
        {
            int pid;
            int request[RESOURCES];

            printf("输入进程号 (0-%d): ", PROCESSES - 1);
            scanf("%d", &pid);

            if (pid < 0 || pid >= PROCESSES)
            {
                printf("无效的进程号!\n");
                break;
            }

            if (finished[pid])
            {
                printf("进程 P%d 已完成!\n", pid);
                break;
            }

            printf("输入资源请求 (A B C): ");
            for (int i = 0; i < RESOURCES; i++)
            {
                scanf("%d", &request[i]);
            }

            request_resources(pid, request);
            break;
        }
        case 2:
            print_state();
            is_safe();
            break;
        case 3:
            printf("退出程序。\n");
            break;
        default:
            printf("无效选择!\n");
        }
    } while (choice != 3);

    return 0;
}